﻿#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <time.h>
#include <algorithm>
#include <assert.h>
#include <fstream>
#include <map>
#include <set>
#include <cmath> 

#define Local 0
#define Linux 1

using namespace std;




struct each_demand_map {
    string timeing; //string is timing 时刻
    int index;     //时间序列编码后的值
    unordered_map<string, int> demand_info_map; //客户需求<客户名, 需求量>
};
struct each_demand_sum {
    int index;  //时间序列编码后的值
    int sum;    //需求之和
};
struct each_edge {
    int index;  //时间序列编码后的值
    int bandwidth_up;
};
bool cmp_sum_down(each_demand_sum a, each_demand_sum b) {
    return (a.sum > b.sum);
}
bool cmp_bandwidth_down(each_edge a, each_edge b) {
    return (a.bandwidth_up > b.bandwidth_up);
}

struct each_Qos_1 {
    int index;//客户名  
    int sum_one;       //权重和
};
bool cmp_sum_1_down(each_Qos_1 a, each_Qos_1 b) {
    return (a.sum_one < b.sum_one);
}

//输入相关
//clint_s为客户序列表
vector<string> clint_s;
//边缘节点名称序列
vector<string> edge_s;
//单时刻客户需求排序
vector<each_Qos_1> client_sort_qos;


vector<vector<int>> Qos_array;
//迭代器的时间序列
vector<each_demand_map> each_demand_res_map;

//描述不同边缘节点的<边缘节点名,<客户名,Qos值>>
unordered_map<string, unordered_map<string, int>> edge_clint_Qos;

//描述带宽的map <边缘节点名，最大带宽值>
unordered_map<string, int> edge_max_band;

vector<each_edge> edge_index;


//根据需求最大进行排序
vector<each_demand_sum> after_sort_demand_sum;
unordered_map<int, int> re_after_sort_demand_sum;
//根据带宽最大进行排序
vector<each_edge> after_sort_bandwidth;

//边缘节点的状态
vector<pair<int, int>> edge_state;

//Qos约束矩阵<客户名，<边缘节点名,是否可用>> 1：可以用   0：不可以用
unordered_map<string, unordered_map<string, int>> edge_clint_Qos_martix;


//输出相关
//按照时刻排序的结果
//<客户节点名,<服务器名,分配带宽>>
vector<unordered_map<string, unordered_map<string, int>>> output_solution;
vector<unordered_map<string, unordered_map<string, int>>> output_solution_r;

vector<map<string, int>> edge_sum_vec;

/*
in:
srcStr : main string
destVect : result vector
strFlag : flag

out:size of result
*/
int splitStringToVect(const string& srcStr, vector<string>& destVect, const string& strFlag)
{
    int pos = srcStr.find(strFlag, 0);
    int startPos = 0;
    int splitN = pos;
    string lineText(strFlag);

    while (pos > -1)
    {
        lineText = srcStr.substr(startPos, splitN);
        startPos = pos + 1;
        pos = srcStr.find(strFlag, pos + 1);
        splitN = pos - startPos;
        destVect.push_back(lineText);
    }
#if Linux
    lineText = srcStr.substr(startPos, srcStr.length() - startPos - 1);
#endif
#if Local
    lineText = srcStr.substr(startPos, srcStr.length() - startPos);
#endif  
    destVect.push_back(lineText);

    return destVect.size();
}
//match word
int* getNext(string p)
{
    int* next = new int[p.length()];
    next[0] = -1;           //while the first char not match, i++,j++
    int j = 0;
    int k = -1;
    while (j < (int)p.length() - 1)
    {
        if (k == -1 || p[j] == p[k])
        {
            j++;
            k++;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
    return next;
}
/*
in:
T: main string (long)
p: sub string (short)

out:
-1: can not find the string
other num:the begin of sub string
*/
int KMP(string T, string p)
{
    int i = 0;
    int j = 0;
    int* next = getNext(T);
    while (i < (int)T.length() && j < (int)p.length())
    {
        if (j == -1 || T[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j == (int)p.length())
    {
        return i - j;
    }
    return -1;
}

/*
in:
path :the path of source data
out:
-1: fail to get Qos
other num: Qos num
*/
int get_Qos_threshold(string& path)
{
    int Qos_threshold = -1;
    string goal_path = path + "/config.ini";
    ifstream Qos_config(goal_path, ios::in);
    if (!Qos_config.is_open())
    {
        cout << "Can not open" << goal_path << endl;
        return -1;
    }
    cout << "open" << goal_path << " successfully!" << endl;
    while (!Qos_config.eof())
    {
        string line_buf;
        getline(Qos_config, line_buf);
        int tmp = KMP(line_buf, "=");
        if (tmp != -1)
        {
            string num_s = line_buf.substr(tmp + 1);
            Qos_threshold = stoi(num_s);
        }
    }
    Qos_config.close();
    return Qos_threshold;
}
/*
in:
path :the path of source data
out:
-1: fail to get demand time slices
other num: demand time slices
*/
int get_demand(string& path)
{
    //    vector<each_demand> res;
    string goal_path = path + "/demand.csv";
    ifstream demand_file(goal_path, ios::in);
    if (!demand_file.is_open())
    {
        cout << "Can not open" << goal_path << endl;
        return -1;
    }
    cout << "open" << goal_path << " successfully!" << endl;
    int count = 0;
    int index_count = 1;
    while (!demand_file.eof())
    {
        string line_buf;
        getline(demand_file, line_buf);
        if (count == 0)
        {
            int tmp = KMP(line_buf, ",");
            string client_name = line_buf.substr(tmp + 1);
            splitStringToVect(client_name, clint_s, ",");
        }
        else
        {
            int tmp = KMP(line_buf, ",");
            if (tmp != -1)
            {
                each_demand_map ed;
                string timeing_each = line_buf.substr(0, tmp);
                ed.timeing = timeing_each;
                ed.index = index_count;
                index_count++;
                string each_demand_s = line_buf.substr(tmp + 1);
                vector<string> each_demand_vec_s;
                splitStringToVect(each_demand_s, each_demand_vec_s, ",");
                int len = each_demand_vec_s.size();
                for (int i = 0; i < len; i++)
                {
                    ed.demand_info_map.emplace(clint_s[i], stoi(each_demand_vec_s[i]));
                }
                each_demand_res_map.push_back(ed);
            }
        }
        count++;
    }
    demand_file.close();
    return each_demand_res_map.size();
}
/*
in:
path :the path of source data
out:
-1: fail to get the size of edge(s)
other num: the size of edge(s)
*/
int get_Qos(string& path)
{
    string goal_path = path + "/qos.csv";
    ifstream Qos_file(goal_path, ios::in);
    if (!Qos_file.is_open())
    {
        cout << "Can not open" << goal_path << endl;
        return -1;
    }
    cout << "open" << goal_path << " successfully!" << endl;
    int count = 0;

    while (!Qos_file.eof())
    {
        string line_buf;
        getline(Qos_file, line_buf);

        if (count > 0)
        {
            int tmp = KMP(line_buf, ",");
            if (tmp != -1)
            {
                string edge_name = line_buf.substr(0, tmp);
                edge_s.push_back(edge_name);
                string edge_name_Qos_data = line_buf.substr(tmp + 1);
                vector<string> edge_name_other_vec_s;
                splitStringToVect(edge_name_Qos_data, edge_name_other_vec_s, ",");
                unordered_map<string, int> tmp;
                int length_clints = edge_name_other_vec_s.size();
                for (int i = 0; i < length_clints; i++)
                {
                    tmp.emplace(clint_s[i], stoi(edge_name_other_vec_s[i]));
                }
                edge_clint_Qos.emplace(edge_name, tmp);
            }

        }
        count++;
    }
    Qos_file.close();
    return edge_clint_Qos.size();
}
/*
in:
path :the path of source data
out:
-1: fail to get the size of edge(s)
other num: the size of edge(s)
*/
int get_site_bandwidth(string& path)
{
    string goal_path = path + "/site_bandwidth.csv";
    ifstream site_bandwidth(goal_path, ios::in);
    if (!site_bandwidth.is_open())
    {
        cout << "Can not open" << goal_path << endl;
        return -1;
    }
    cout << "open" << goal_path << " successfully!" << endl;
    int count = 0;

    while (!site_bandwidth.eof())
    {
        string line_buf;
        getline(site_bandwidth, line_buf);
        if (count > 0)
        {
            int tmp = KMP(line_buf, ",");
            if (tmp != -1)
            {
                string edge_name = line_buf.substr(0, tmp);
                string max_bandwidth_s = line_buf.substr(tmp + 1);
                int max_bandwidth = stoi(max_bandwidth_s);
                edge_max_band.emplace(edge_name, max_bandwidth);
            }
        }
        count++;
    }
    site_bandwidth.close();
    return edge_max_band.size();
}
//将输出打印到控制台上
void print_outfile()
{   //string& out_path
    //string goal_path = out_path + "/output/solution.txt";
    //ofstream out_put_file(goal_path, ios::out);
    int length0 = output_solution.size();
    for (int i = 0; i < length0; i++)
    {
        unordered_map<string, unordered_map<string, int>> each_timings_all_map = output_solution[i];
        for (auto& kv : each_timings_all_map)
        {
            string key = kv.first;
            cout << key << ":";
            unordered_map<string, int> each_timings_each_map = kv.second;
            int len = each_timings_each_map.size() - 1;
            if (len == -1)
            {
                cout << "\n";
            }
            else {
                int len_count = 0;
                for (auto& kv_in : each_timings_each_map)
                {
                    string edge_name = kv_in.first;
                    int num = kv_in.second;
                    cout << "<" << edge_name << "," << num << ">";
                    if (len_count < len)
                    {
                        cout << ",";
                    }
                    else if (len_count == len)
                    {
                        cout << "\n";
                    }
                    len_count++;
                }
            }
        }
    }

}

//输出方案
void print_all_data()
{
    int length0 = edge_s.size();
    for (int i = 0; i < length0; i++) //N
    {
        string  name = edge_s[i];
        cout << name << " = [";
        int length1 = output_solution.size(); //t
        for (int j = 0; j < length1; j++)
        {
            int edge_timing_used = 0;
            unordered_map<string, unordered_map<string, int>> map_tmp = output_solution[j];
            int length2 = map_tmp.size();
            for (int i = 0; i < length2; i++)
            {
                unordered_map<string, int> map_in = map_tmp[clint_s[i]];
                for (auto& kv : map_in)
                {
                    if (kv.first == name)
                    {
                        edge_timing_used += kv.second;
                    }
                }
            }
            cout << edge_timing_used << " ";
        }
        cout << "]" << endl;
    }
}

//将输出打印到对应路径下的solution.txt文件
void print_outfile(string out_path)
{
    string goal_path = out_path + "/output/solution.txt";
    ofstream out_put_file(goal_path, ios::out);
    if (!out_put_file.is_open())
    {
        cout << "Can not open" << goal_path << endl;
        return;
    }
    cout << "open" << goal_path << " successfully!" << endl;
    int length0 = output_solution.size();
    for (int i = 0; i < length0; i++)
    {
        unordered_map<string, unordered_map<string, int>> each_timings_all_map = output_solution[i];
        for (auto& kv : each_timings_all_map)
        {
            string key = kv.first;
            out_put_file << key << ":";
            unordered_map<string, int> each_timings_each_map = kv.second;
            int len = each_timings_each_map.size() - 1;
            if (len == -1)
            {
                out_put_file << "\n";
            }
            else {
                int len_count = 0;
                for (auto& kv_in : each_timings_each_map)
                {
                    string edge_name = kv_in.first;
                    int num = kv_in.second;
                    //if (!num) continue;
                    out_put_file << "<" << edge_name << "," << num << ">";
                    if (len_count < len)
                    {
                        out_put_file << ",";
                    }
                    else if (len_count == len)
                    {
                        out_put_file << "\n";
                    }
                    len_count++;
                }
            }
        }
    }

    out_put_file.close();

}

//排序所有时间序列的需求，返回按照时间序列的顺序
vector<each_demand_sum> sort_demand_sum()
{
    vector<each_demand_sum> res;
    int length = each_demand_res_map.size(); //each_demand_res_map  时间序列
    for (int i = 0; i < length; i++)
    {
        each_demand_sum tmp;
        tmp.index = each_demand_res_map[i].index;
        int sum_tmp = 0;
        unordered_map<string, int> map_t = each_demand_res_map[i].demand_info_map;
        for (auto& kv : map_t)
        {
            sum_tmp = sum_tmp + kv.second;
        }
        tmp.sum = sum_tmp;
        res.push_back(tmp);
    }
    sort(res.begin(), res.end(), cmp_sum_down);
    return res;
}

vector<each_edge> sort_edge_bandwidth_up()
{
    vector<each_edge> res;
    int length = edge_max_band.size(); //each_demand_res_map  时间序列
    int edge_index = 1;
    for (int i = 0; i < length; i++)
    {
        each_edge tmp;
        tmp.index = edge_index++;
        tmp.bandwidth_up = edge_max_band[edge_s[i]];
        res.push_back(tmp);
    }
    sort(res.begin(), res.end(), cmp_bandwidth_down);

    return res;
}

//得到带宽迭代器，按照edge_s的顺序
vector<int> pre_get_band_vec()
{
    vector<int> residue;
    int len0 = edge_max_band.size();
    for (int i = 0; i < len0; i++)
    {
        string s = edge_s[i];
        if (edge_max_band.end() != edge_max_band.find(s))
        {
            residue.push_back(edge_max_band[s]);
        }
    }
    return  residue;
}

//输入为Qos阈值
//得到Qos_array矩阵，其中1代表不约束，相反为0
//Qos_array[M][N]    M为客户数量，N为服务器数量 M与N排序分别参考clint_s与edge_s的顺序
void pre_get_clints2edge_Qos_martix(int Qos_th)
{
    int len1 = clint_s.size();
    int len0 = edge_s.size();
    Qos_array.resize(len1);
    for (int k = 0; k < len1; ++k) {
        Qos_array[k].resize(len0);//每行为c列
    }

    for (int i = 0; i < len0; i++) //N
    {
        unordered_map<string, int> map = edge_clint_Qos[edge_s[i]];

        for (int j = 0; j < len1; j++) //M
        {
            if (Qos_th - map[clint_s[j]] > 0)
            {
                Qos_array[j][i] = 1;
            }
            else
            {
                Qos_array[j][i] = 0;
            }
        }
    }
    return;
}

//计算Qos与服务器带宽相乘 描述当前网络质量
//返回值为从小到大的名称序列
//
void get_sort_Qos_1()
{
    int len0 = Qos_array.size();      //M
    int len1 = Qos_array[0].size();   //N
    for (int i0 = 0; i0 < len0; i0++)
    {
        each_Qos_1 tmp({ 0, 0 });
        tmp.index = i0;
        for (int i1 = 0; i1 < len1; i1++)
        {
            tmp.sum_one += Qos_array[i0][i1];
        }
        client_sort_qos.push_back(tmp);

    }
    // cmp_weight_down
    sort(client_sort_qos.begin(), client_sort_qos.end(), cmp_sum_1_down);
    return;
}

//贪心策略的算法
void greed_demand_based_timing_per(each_demand_map _eeach_demand_map, const vector<int>& _max_site_band_vec)
{
    /*for (int a : _max_site_band_vec)
    {
        cout << a << " ";
    }
    cout << endl;*/
    vector<int> tmp_vec_res = _max_site_band_vec;
    vector<int> tmp_vec_res_per(tmp_vec_res);
    unordered_map<string, unordered_map<string, int>> output_map;
    int t_size = each_demand_res_map.size();
    int frequency1 = ceil(t_size * 0.05) - 1;
    int len = clint_s.size();

    int len1 = edge_s.size();         // N   边缘节点  

    vector<int> save_s;
    for (int i = 0; i < len1; i++)
    {
        save_s.push_back(edge_state[i].first);
    }


    for (int i = 0; i < len; i++)
    {
        int i_index = client_sort_qos[i].index;
        unordered_map<string, int> each_client;
        vector<int> arry_tmp_res = Qos_array[i_index]; //寻找Qos的数组，第i种情况下的约束
        long long  sum_band = 0;

        for (int i0 = 0; i0 < len1; i0++)
        {
            sum_band += arry_tmp_res[i0] * tmp_vec_res[i0];
        }
        for (int i0 = 0; i0 < len1; i0++)
        {
            if (!save_s[i0] && arry_tmp_res[i0])
                sum_band -= tmp_vec_res[i0];
        }

        int M_need = _eeach_demand_map.demand_info_map[clint_s[i_index]];     //寻找第i个客户的带宽需求量
        int M_need_r = M_need;
        for (int s = 0; s < len1; s++)
        {
            int j = after_sort_bandwidth[s].index;
            if (!arry_tmp_res[j - 1]) continue;
            if (edge_state[j - 1].first) continue;
            if (!tmp_vec_res_per[j - 1]) continue;
             
            if (tmp_vec_res_per[j - 1] - M_need_r >= 0)
            {
                tmp_vec_res_per[j - 1] -= M_need_r; //更新剩余带宽
                each_client.emplace(edge_s[j - 1], M_need_r);
                M_need_r = 0;
                edge_state[j - 1].second++;
                if (edge_state[j - 1].second == frequency1)
                    edge_state[j - 1].first = 1;
                break;
            }
            else
            {
                if (tmp_vec_res_per[j - 1] > 0)
                {
                    each_client.emplace(edge_s[j - 1], tmp_vec_res_per[j - 1]);
                    M_need_r -= tmp_vec_res_per[j - 1];
                    tmp_vec_res_per[j - 1] = 0;
                    edge_state[j - 1].second++;
                    if (edge_state[j - 1].second == frequency1)
                        edge_state[j - 1].first = 1;
                }
            }
        }

        //for (int s = 0; s < len1; s++)
        //{
        //    int j = after_sort_bandwidth[s].index;
        //    if (tmp_vec_res_per[j - 1] != tmp_vec_res[j - 1] && !edge_state[j - 1].first)
        //        edge_state[j - 1].second++;
        //    if (edge_state[j - 1].second == frequency1)
        //        edge_state[j - 1].first = 1;
        //}
        double alfa = 1.0;
        double M_need_d = M_need_r;
        double sum_band_d = sum_band;
        alfa = M_need_d / sum_band_d;
        if (M_need_r)
        {
            for (int k = 0; k < len1; k++)
            {
                if (!save_s[k]) continue;
                if (arry_tmp_res[k] > 0)   //当前服务器还有剩余带宽（Qos不被约束）
                {
                    tmp_vec_res_per[k] = ceil(tmp_vec_res[k] * alfa);

                    if (tmp_vec_res_per[k] - M_need_r >= 0)
                    {
                        tmp_vec_res_per[k] -= M_need_r; //更新剩余带宽
                        each_client.emplace(edge_s[k], M_need_r);
                        break;
                    }
                    else if (tmp_vec_res_per[k] > 0)
                    {
                        each_client.emplace(edge_s[k], tmp_vec_res_per[k]);
                        M_need_r = M_need_r - tmp_vec_res_per[k];
                        tmp_vec_res_per[k] = 0;
                    }

                }
            }
        }
        output_map.emplace(clint_s[i_index], each_client);
    }
    output_solution_r.push_back(output_map);
}

//计算成本函数
//主要是根据output_solution迭代器的数据进行计算 输入：无，输出：分数
//output_solution的长度为时间片
int print_95_cost()
{
    set<string> edge_name_table;
    vector<string> edge_name_vec;
    int score = 0;
    int length = output_solution.size();

    for (int i = 0; i < length; i++)
    {
        map<string, int> edge_sum;
        unordered_map<string, unordered_map<string, int>> unordermap_tmp_i = output_solution[i];
        for (auto& kv : unordermap_tmp_i)
        {
            unordered_map<string, int>  unordermap_edge = kv.second;
            for (auto& kv_in : unordermap_edge)
            {
                if (edge_sum.count(kv_in.first) == 0)  //未有该key（edge）
                {
                    edge_sum[kv_in.first] = kv_in.second;
                    if (edge_name_table.find(kv_in.first) == edge_name_table.end())
                    {
                        edge_name_table.insert(kv_in.first);
                        edge_name_vec.push_back(kv_in.first);
                    }
                }
                else                                  //存在key
                {
                    edge_sum[kv_in.first] = edge_sum[kv_in.first] + kv_in.second;
                }
            }
        }
        edge_sum_vec.push_back(edge_sum);
    }
    //edge_name_vec 记录edge相关的顺序
    int edge_name_vec_len = edge_name_vec.size(); //M
    int r_length_95 = ceil(length * 0.95);    //95%分位点

    for (int i1 = 0; i1 < edge_name_vec_len; i1++)
    {
        vector<int> tmp_edge(length, 0);
        for (int j1 = 0; j1 < length; j1++)
        {
            string str = edge_name_vec[i1];
            int sum = 0;
            //若可以搜索到插入数值 若不可以被搜索到 则插入0
            if (edge_sum_vec[j1].end() != edge_sum_vec[j1].find(str))
            {
                sum = edge_sum_vec[j1][str];
            }
            tmp_edge[j1] = sum;
        }
        if (tmp_edge.size() == length)
        {
            sort(tmp_edge.begin(), tmp_edge.end()); //升序算分排序
            score += tmp_edge[r_length_95 - 1];      //取整后的百分之95位置的索引
        }
    }
    cout << "the cost is :" << score << endl;
    return score;
}

void printf_sort_result(const vector<each_edge>& after_sort_bandwidth, const vector<int>& max_site_band_vec)
{
    for (int i = 0; i < 100; i++)
    {
        cout << after_sort_bandwidth[i].index << " " << after_sort_bandwidth[i].bandwidth_up << " " << max_site_band_vec[i] << endl;
    }
    return;
}

void printf_sort_result(const vector<each_demand_sum>& after_sort_demand_sum)
{
    for (const auto eds : after_sort_demand_sum)
    {
        cout << eds.index << " ";
    }
    return;
}

//输出方案
void print_all_data(string out_path)
{
    string goal_path = out_path + "/my_result.csv";
    ofstream out_put_file(goal_path, ios::out);
    if (!out_put_file.is_open())
    {
        cout << "Can not open" << goal_path << endl;
        return;
    }
    cout << "open" << goal_path << " successfully!" << endl;
    int length0 = edge_s.size();
    for (int i = 0; i < length0; i++) //N
    {
        string  name = edge_s[i];
        out_put_file << name << ",";
        int length1 = output_solution.size(); //t
        for (int j = 0; j < length1; j++)
        {
            int edge_timing_used = 0;
            unordered_map<string, unordered_map<string, int>> map_tmp = output_solution[j];
            int length2 = map_tmp.size();
            for (int i = 0; i < length2; i++)
            {
                unordered_map<string, int> map_in = map_tmp[clint_s[i]];
                for (auto& kv : map_in)
                {
                    if (kv.first == name)
                    {
                        edge_timing_used += kv.second;
                    }
                }
            }
            out_put_file << edge_timing_used << ",";
        }
        out_put_file << endl;
    }
    out_put_file.close();
}

//输出排序后的方案
void print_all_sort_data(string out_path)
{
    string goal_path = out_path + "/my_result_sort.csv";
    ofstream out_put_file(goal_path, ios::out);
    if (!out_put_file.is_open())
    {
        cout << "Can not open" << goal_path << endl;
        return;
    }
    cout << "open" << goal_path << " successfully!" << endl;
    int length0 = edge_s.size();
    for (int i = 0; i < length0; i++) //N
    {
        string  name = edge_s[i];
        int length1 = output_solution.size(); //t
        vector<int> edge_timing_used_vec;
        for (int j = 0; j < length1; j++)
        {

            int edge_timing_used = 0;
            unordered_map<string, unordered_map<string, int>> map_tmp = output_solution[j];
            int length2 = map_tmp.size();
            for (int i = 0; i < length2; i++)
            {
                unordered_map<string, int> map_in = map_tmp[clint_s[i]];
                for (auto& kv : map_in)
                {
                    if (kv.first == name)
                    {
                        edge_timing_used += kv.second;
                    }
                }
            }
            edge_timing_used_vec.push_back(edge_timing_used);
        }
        sort(edge_timing_used_vec.begin(), edge_timing_used_vec.end());
        out_put_file << name << ",";
        for (auto& tmp : edge_timing_used_vec)
        {
            out_put_file << tmp << ",";
        }
        out_put_file << endl;
    }


    out_put_file.close();
}

//解的合法性判断
bool is_leagel_print_error()
{
    //1 每个服务器小于等于上限制
    //2 每个客户需求被满足
    bool flag = true;
    int len = output_solution.size();
    for (int i = 0; i < len; i++)
    {
        unordered_map<string, unordered_map<string, int>>  each_timing = output_solution[i];
        each_demand_map each_demand_tmp = each_demand_res_map[i];
        int len0 = each_timing.size();  //M个客户

        for (int j = 0; j < len0; j++)
        {
            int sum_tmp = 0;
            unordered_map<string, int> each_edge_s = each_timing[clint_s[j]];
            for (auto& kv : each_edge_s)
            {
                if (kv.second > edge_max_band[kv.first])
                {
                    cout << "timing index" << i + 1 << ":" << kv.first << "'s demand out of limit" << endl;
                    flag = false;
                }
                else
                {
                    sum_tmp += kv.second;
                }
            }
            if (sum_tmp != each_demand_tmp.demand_info_map[clint_s[j]])
            {
                cout << "timing index" << i + 1 << ":" << clint_s[j] << "'s demand can't be satisfied" << endl;
                cout << "Current:" << sum_tmp << " " << "target:" << each_demand_tmp.demand_info_map[clint_s[j]] << endl;
                flag = false;
            }
        }
    }

    return flag;
}

bool is_leagel()
{
    //1 每个服务器小于等于上限制
    //2 每个客户需求被满足

    int len = output_solution.size();
    for (int i = 0; i < len; i++)
    {
        unordered_map<string, unordered_map<string, int>>  each_timing = output_solution[i];
        each_demand_map each_demand_tmp = each_demand_res_map[i];
        int len0 = each_timing.size();  //M个客户

        for (int j = 0; j < len0; j++)
        {
            int sum_tmp = 0;
            unordered_map<string, int> each_edge_s = each_timing[clint_s[j]];
            for (auto& kv : each_edge_s)
            {
                if (kv.second > edge_max_band[kv.first])
                {
                    return false;
                }
                else
                {
                    sum_tmp += kv.second;
                }
            }
            if (sum_tmp != each_demand_tmp.demand_info_map[clint_s[j]])
            {
                return false;
            }
        }
    }
    return true;
}

void test_readFiles(string path)
{
    cout << "test reading files !" << endl;
    int get_Qos_threshold_res = get_Qos_threshold(path);
    cout << "test_Qos_max  = " << get_Qos_threshold_res << endl;
    int get_demand_res = get_demand(path);
    cout << "test_demand time slices =" << get_demand_res << endl;
    int edge_num0 = get_Qos(path);
    cout << "edge_num from Qos.csv = " << edge_num0 << endl;
    int edge_num1 = get_site_bandwidth(path);
    cout << "edge_num from site_bandwidth.csv = " << edge_num1 << endl;
    pre_get_clints2edge_Qos_martix(get_Qos_threshold_res);
    cout << "finish!" << endl;
}

bool cmpare(int a, int b)
{
    return a > b;
}

void test_algorithm(string path)
{
    vector<int> max_site_band_vec = pre_get_band_vec();
    int length = each_demand_res_map.size();
    int t_len = each_demand_res_map.size();
    output_solution.resize(t_len);
    get_sort_Qos_1();
    after_sort_demand_sum = sort_demand_sum();
    after_sort_bandwidth = sort_edge_bandwidth_up();
 

    for (int i = 0; i < max_site_band_vec.size(); i++)
    {
        edge_state.push_back({ 0, 0 });
    }

    for (int i = 0; i < length; i++)
    {
        int t = after_sort_demand_sum[i].index;
        greed_demand_based_timing_per(each_demand_res_map[t - 1], max_site_band_vec);
        output_solution[t - 1] = output_solution_r[i];
    }
    print_outfile(path);

}

int main() {
#if Local
    string input_path = "C:\\Users/Zhang/Desktop/2022/data";
    string output_path = "C:\\Users/Zhang/Desktop/2022/data";
    //string input_path = "D:\\华为软挑/simulated_data";
    //string output_path = "D:\\华为软挑/simulated_data";
    //string input_path = "D:\\华为软挑/pressure_data";
    //string output_path = "D:\\华为软挑/pressure_data";
#endif 
#if Linux
    string input_path = "/data";
    string output_path = "";
#endif 
    clock_t s_time, e_time;
    s_time = clock();

    test_readFiles(input_path);
    test_algorithm(output_path);


    e_time = clock();
    cout << "Total time:" << (double)(e_time - s_time) / CLOCKS_PER_SEC << "S" << endl;


    return 0;
}

